class Solution {
    unordered_map<long long,long long> hash;
public:
    int integerReplacement(int n) {
        return dfs(n);
    }
    int dfs(long long n)
    {
        if(hash.count(n)) return hash[n];
        if(n==1) return 0;
        if(n%2==0)
        {
            hash[n]=1+dfs(n/2);
            return hash[n];
        }
        else
        {
            hash[n]=1+min(dfs(n-1),dfs(n+1));
            return hash[n];
        }
    }
};
